/*
    非递归遍历二叉树的方法通常使用堆栈和队列来存储中间状态，避免了递归的栈深度限制。下面是非递归实现二叉树的前序、中序、后序和层序遍历的代码示例。
*/

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

// 堆栈结构用于非递归遍历
typedef struct StackNode {
    TreeNode* treeNode;
    struct StackNode* next;
} StackNode;

typedef struct Stack {
    StackNode* top;
} Stack;

// 创建堆栈
Stack* createStack() {
    Stack* stack = (Stack*)malloc(sizeof(Stack));
    stack->top = NULL;
    return stack;
}

// 入栈
void push(Stack* stack, TreeNode* treeNode) {
    StackNode* newNode = (StackNode*)malloc(sizeof(StackNode));
    newNode->treeNode = treeNode;
    newNode->next = stack->top;
    stack->top = newNode;
}

// 出栈
TreeNode* pop(Stack* stack) {
    if (stack->top == NULL) {
        return NULL;
    }
    StackNode* temp = stack->top;
    TreeNode* treeNode = temp->treeNode;
    stack->top = stack->top->next;
    free(temp);
    return treeNode;
}

// 检查堆栈是否为空
bool isStackEmpty(Stack* stack) {
    return stack->top == NULL;
}

// 创建二叉树节点
TreeNode* createNode(int data) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// 插入数据到二叉树
TreeNode* insert(TreeNode* root, int data) {
    if (root == NULL) {
        return createNode(data);
    }

    if (data < root->data) {
        root->left = insert(root->left, data);
    } else {
        root->right = insert(root->right, data);
    }

    return root;
}

// 非递归前序遍历
void preOrderTraversal(TreeNode* root) {
    if (root == NULL) return;

    Stack* stack = createStack();
    push(stack, root);

    while (!isStackEmpty(stack)) {
        TreeNode* currentNode = pop(stack);
        printf("%d ", currentNode->data);

        // 先推右子节点，然后推左子节点
        if (currentNode->right != NULL) {
            push(stack, currentNode->right);
        }
        if (currentNode->left != NULL) {
            push(stack, currentNode->left);
        }
    }

    free(stack);
    printf("\n");
}

// 非递归中序遍历
void inOrderTraversal(TreeNode* root) {
    Stack* stack = createStack();
    TreeNode* currentNode = root;

    while (currentNode != NULL || !isStackEmpty(stack)) {
        // 一直向左走，并入栈
        while (currentNode != NULL) {
            push(stack, currentNode);
            currentNode = currentNode->left;
        }

        currentNode = pop(stack); // 取出节点并处理
        printf("%d ", currentNode->data);

        currentNode = currentNode->right; // 转向右子树
    }

    free(stack);
    printf("\n");
}

// 非递归后序遍历
void postOrderTraversal(TreeNode* root) {
    if (root == NULL) return;

    Stack* stack1 = createStack(); // 辅助栈
    Stack* stack2 = createStack(); // 结果栈
    push(stack1, root);

    while (!isStackEmpty(stack1)) {
        TreeNode* currentNode = pop(stack1);
        push(stack2, currentNode);

        // 先推左子节点，然后推右子节点
        if (currentNode->left != NULL) {
            push(stack1, currentNode->left);
        }
        if (currentNode->right != NULL) {
            push(stack1, currentNode-> right);
        }
    }

    // 从结果栈弹出，即为后序遍历
    while (!isStackEmpty(stack2)) {
        TreeNode* currentNode = pop(stack2);
        printf("%d ", currentNode->data);
    }

    free(stack1);
    free(stack2);
    printf("\n");
}

// 非递归层序遍历
typedef struct QueueNode {
    TreeNode* treeNode;
    struct QueueNode* next;
} QueueNode;

typedef struct Queue {
    QueueNode* front;
    QueueNode* rear;
} Queue;

Queue* createQueue() {
    Queue* queue = (Queue*)malloc(sizeof(Queue));
    queue->front = queue-> rear = NULL;
    return queue;
}

void enqueue(Queue* queue, TreeNode* treeNode) {
    QueueNode* newQueueNode = (QueueNode*)malloc(sizeof(QueueNode));
    newQueueNode->treeNode = treeNode;
    newQueueNode-> next = NULL;
    if (queue-> rear == NULL) {
        queue->front = queue-> rear = newQueueNode;
    } else {
        queue-> rear-> next = newQueueNode;
        queue-> rear = newQueueNode;
    }
}

TreeNode* dequeue(Queue* queue) {
    if (queue-> front == NULL) {
        return NULL;
    }
    QueueNode* temp = queue-> front;
    TreeNode* treeNode = temp-> treeNode;
    queue-> front = queue-> front-> next;
    if (queue-> front == NULL) {
        queue-> rear = NULL;
    }
    free(temp);
    return treeNode;
}

bool isQueueEmpty(Queue* queue) {
    return queue-> front == NULL;
}

void levelOrderTraversal(TreeNode* root) {
    if (root == NULL) return;

    Queue* queue = createQueue();
    enqueue(queue, root);

    while (!isQueueEmpty(queue)) {
        TreeNode* currentNode = dequeue(queue);
        printf("%d ", currentNode-> data);

        if (currentNode-> left != NULL) {
            enqueue(queue, currentNode-> left);
        }
        if (currentNode-> right != NULL) {
            enqueue(queue, currentNode-> right);
        }
    }

    free(queue);
    printf("\n");
}

// 主函数
int main() {
    TreeNode* root = NULL;

    int values[] = {10, 5, 15, 3, 7, 13, 17}; // 示例数据
    for (int i = 0; i < 7; i++) {
        root = insert(root, values[i]); // 创建二叉树
    }

    printf("Pre-order traversal (Non-Recursive): "); 
    preOrderTraversal(root); // 非递归前序遍历
    printf("\n");

    printf("In-order traversal (Non-Recursive): "); 
    inOrderTraversal(root); // 非递归中序遍历
    printf("\n");

    printf("Post-order traversal (Non-Recursive): "); 
    postOrderTraversal(root); // 非递归后序遍历
    printf("\n");

    printf("Level-order traversal: "); 
    levelOrderTraversal(root); // 层序遍历
    printf("\n");

    return 0;
}
